package mo.offer_special;

import mo.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class L056 {

    private List<Integer> nodes = new ArrayList<>();

    public boolean findTarget(TreeNode root, int k) {
        dfs(root);
        int left = 0;
        int size = nodes.size();
        int right = size - 1;
        while (left < right) {
            int sum = nodes.get(left) + nodes.get(right);
            if (sum == k) {
                return true;
            } else if (sum < k) {
                left++;
            } else {
                right--;
            }
        }
        return false;
    }

    private void dfs(TreeNode root) {
        if (root != null) {
            dfs(root.left);
            nodes.add(root.val);
            dfs(root.right);
        }
    }

    public static void main(String[] args) {
        L056 test = new L056();
        TreeNode root = new TreeNode(8);
        TreeNode left = new TreeNode(6);
        TreeNode right = new TreeNode(10);
        root.left = left;
        root.right = right;
        left.left = new TreeNode(5);
        left.right = new TreeNode(7);
        right.left = new TreeNode(9);
        right.right = new TreeNode(11);
        System.out.println(test.findTarget(root, 12));
    }

}
